package com.uow.algdemo.algorithms;

import java.util.ArrayList;
import java.util.List;

import android.util.Log;

/**
 * This class will receive data of graphs and calculate shortest path or minimum spanning tree algorithms and generate animation steps.
 */
public class Graph
{

	private final int MOUSTMAX = 1000;
	private List<Integer> START = new ArrayList<Integer>();
	private List<Integer> END = new ArrayList<Integer>();
    /**
     * This array contains edges of graph and the length between two points.
     */
	private int[][] edges;
    /**
     * This array contains steps of shortest path or minimum spanning tree solution.
     */
	private List<int[][]> steps = new ArrayList<int[][]>();
	
    /**
     * @param newPoints Name points.
     * @param newEdges Edges of graph and the length between two points.
     */
	public Graph(int[][] newEdges)
	{
		edges = newEdges;
	}
	/**
	 * @return The steps of shortest path or minimum spanning tree solution.
	 */
	public List<int[][]> getSteps()
	{
		return steps;
	}
	/**
     * This method records steps for highlight one edge.
     * @param indexPointA Index of first point.
     * @param indexPointB Index of second point.
     */
	private void highlight(int indexPointA, int indexPointB)
	{
		int[][] tmp = new int[3][1];
		tmp[0][0] = 0;
		tmp[1][0] = indexPointA;
		tmp[2][0] = indexPointB;
		steps.add(tmp);
	}
    /**
     * This method records steps for select one edge on graph.
     * @param indexPointA Index of first point.
     * @param indexPointB Index of second point.
     */
	private void select(int indexPointA, int indexPointB)
	{
		int[][] tmp = new int[3][1];
		tmp[0][0] = 1;
		tmp[1][0] = indexPointA;
		tmp[2][0] = indexPointB;
		steps.add(tmp);
	}
    /**
     * This method records steps for unselect one edge on graph.
     * @param indexPointA Index of first point.
     * @param indexPointB Index of second point.
     */
	/*private void unselect(int indexPointA, int indexPointB)
	{
		int[][] tmp = new int[3][1];
		tmp[0][0] = 2;
		tmp[1][0] = indexPointA;
		tmp[2][0] = indexPointB;
		steps.add(tmp);
	}*/
    /**
     * This method records steps for delete one edge from graph.
     * @param indexPointA Index of first point.
     * @param indexPointB Index of second point.
     */
	/*private void delete(int indexPointA, int indexPointB)
	{
		int[][] tmp = new int[3][1];
		tmp[0][0] = 3;
		tmp[1][0] = indexPointA;
		tmp[2][0] = indexPointB;
		steps.add(tmp);
	}*/
	/**
     * This method find the shortest path use Dijkstra's algorithm and records all steps in list of steps.
     */
	public void shortestDijkstra(int start, int end)
	{
		int []d = new int[11];
		int []p = new int[11];
		int [][]l = new int[11][11];
		boolean[]c = new boolean[11];
		int n = 10;

		for(int i = 0; i < 10; i++)
		{
			for(int j = 0; j < 10; j++)
			{
				l[i+1][j+1] = edges[i][j];
			}
		}
				
		for(int i = 1; i <= n; i++)
		{
			c[i] = true;
			d[i] = l[1][i];
			p[i] = 1;
		}
		
		d[1] = 0;
		c[1] = false;

		for(int i = 2; i <= n; i++)
		{
			int v = 1;
			int tmp = MOUSTMAX;
			for(int j = 1; j <= n; j++)
			{
				if(c[j] == true && d[j] < tmp)
				{
					v = j;
					tmp = d[j];
				}
			}

			c[v] = false;

			for(int w = 2; w <= n; w++)
			{
				if(c[w] == true && l[v][w] != MOUSTMAX)
				{
					if(d[w] > d[v] + l[v][w])
					{
						d[w] = d[v] + l[v][w];
						p[w] = v;
					}
				}
			}
		}
		
		int []que = new int[100];
		int tot = 1;
		que[tot] = end;
		tot++;
		int tmp = p[end];

		while(tmp != start)
		{
			que[tot] = tmp;
			tot++;
			tmp = p[tmp];
		}
		que[tot] = start;
		for(int i=tot; i>=1; --i)
		{
			if(i != 1)
			{
				select(que[i] - 1,que[i-1] - 1);
			}
		}
	}

	/**
     * This method find the minimum spanning tree use Prim's algorithm and records all steps in list of steps.
     */
	public void spanningTreePrim()
	{
		int[][] array = edges;
		boolean[] points = new boolean[10];
		int count = 0;
		for (int i = 0; i < array.length; i++)
		{
			for (int j = 0; j < array.length; j++)
			{
				if (array[i][j] != MOUSTMAX)
				{
					points[i] = true;
					points[j] = true;
				}
			}
		}
		
		for(int i = 0; i < 10; i++)
		{
			if(points[i])
				count++;
		}

		START.add(0);

		int varx = 100, vary = 100;

		while(true)
		{
			int min = 1000;
			for(int i = 0; i < START.size(); i++)
			{
				int minl = array[0][0];
				for(int j = 0; j < array.length; j++)
				{
					if(array[START.get(i)][j] < 100)
					{
						highlight(START.get(i), j);
					}

					if(array[START.get(i)][j] <= minl)
					{
						minl = array[START.get(i)][j];
					}
				}

				if(min > minl)
				{
					min = minl;
					for(int m = 0; m < array.length; m++)
					{
						for(int n = 0; n < array.length; n++)
						{
							if(array[m][n] == min)
							{
								array[m][n] = MOUSTMAX;
								varx = m;
								vary = n;
								break;
							}
						}
					}
				}
			}

			select(varx,vary);
			Log.v("Prim", varx +  "-" + vary);

			if(!START.contains(varx))
			{
				START.add(varx);
			}
			if(!START.contains(vary))
			{
				START.add(vary);
			}
			if(START.size() == count)
			{
				break;
			}
		}
		START.clear();
		END.clear();
	}
	/**
     * This method find the minimum spanning tree use Kruskal's algorithm and records all steps in list of steps.
     */
	public void spanningTreeKruskal()
	{
		int[][] array = edges;

		int count = 0;
		for (int i = 0; i < array.length; i++)
		{
			for (int j = 0; j < array.length; j++)
			{
				if (array[i][j] != MOUSTMAX)
				{
					array[j][i] = MOUSTMAX;
					count++;
				}
			}
		}

		while (count > 0)
		{
			int min = array[0][0];
			for (int i = 0; i < array.length; i++)
			{
				for (int j = 0; j < array.length; j++)
				{
					if(array[i][j] < 100)
					{
						highlight(i,j);
					}
					if (array[i][j] < min)
					{
						min = array[i][j];
					}
				}
			}

			int varx = Integer.MAX_VALUE;
			int vary = Integer.MAX_VALUE;

			for (int i = 0; i < array.length; i++)
			{
				for (int j = 0; j < array.length; j++)
				{
					if (array[i][j] == min)
					{
						array[i][j] = MOUSTMAX;
						varx = i;
						vary = j;
						i=j=200;
					}
				}
			}

			if (END.size() == 0)
			{
				select(varx,vary);
				END.add(varx);
				END.add(vary);
			}
			else
			{
				if (!(END.contains(varx) && END.contains(vary) || START.contains(varx) && START.contains(vary)))
				{
					if (END.contains(varx) && START.contains(vary))
					{
						select(varx,vary);
						for (int char1 : START)
						{
							if (!END.contains(char1))
							{
								END.add(char1);
							}
						}
						START.clear();
					}
					if (START.contains(varx) && END.contains(vary))
					{
						select(varx,vary);
						for (int char1 : START)
						{
							if (!END.contains(char1))
							{
								END.add(char1);
							}
						}
						START.clear();
					}
					if ((!START.contains(varx)) && (!END.contains(varx)) && END.contains(vary))
					{
						select(varx,vary);
						END.add(varx);
					}
					if (START.contains(varx) && (!END.contains(vary)) && (!START.contains(vary)))
					{
						select(varx,vary);
						START.add(varx);
					}

					if (!END.contains(varx) && !END.contains(vary))
					{
						select(varx,vary);
						if (!START.contains(varx) && !START.contains(vary))
						{
							START.add(varx);
							START.add(vary);
						}
						if (START.contains(varx) && !START.contains(vary))
						{
							START.add(vary);
						}
						if (!START.contains(varx) && START.contains(vary))
						{
							START.add(varx);
						}
					}
				}
			}
			count--;
		}
		START.clear();
		END.clear();
	}
}
